Public key data communication systems are used to transfer information between a pair of correspondents. At least part of the information exchanged is enciphered by a predetermined mathematical operation by the sender and the recipient may perform a complementary mathematical operation to decipher the information.
A typical example of such a system is a digital signature protocol. Digital signatures are used to confirm that a message has been sent by a particular party and that the contents have not been altered during transmission.
A widely used set of signature protocols utilizes the El Gamal public key signature scheme that signs a message with the sender's private key. The recipient may then recover the message with the sender's public key.
Various protocols exist for implementing such a scheme and some have been widely used. In each case however the recipient is required to perform a computation to verify the signature. Where the recipient has adequate computing power this does not present a particular problem but where the recipient has limited computing power, such as in a “Smart card” application, the computations may introduce delays in the verification process.
Public key schemes may be implemented using one of a number of multiplicative groups in which the discrete log problem appears intractable but a particularly robust implementation is that utilizing the characteristics of points on an elliptic curve over a finite field. This implementation has the advantage that the requisite security can be obtained with relatively small orders of field compared with, for example, implementations in Zp* and therefore reduces the bandwidth required for communicating the signatures.
In a typical implementation a signature component s has the form:s=ae+k(mod n)where:P is a point on the curve which is a predefined parameter of the systemk is a random integer selected as a short term private or session key, and has a corresponding short term public key R=kPa is the long term private key of the sender and has a corresponding public key aP=Qe is a secure hash, such as the SHA hash function, of a message m and short term public key R, andn is the order of the curve.
The sender sends to the recipient a message including m, s, and R and the signature is verified by computing the value −(sP−eQ) which should correspond to R. If the computed values correspond then the signature is verified.
In order to perform the verification it is necessary to compute a number of point multiplications to obtain sP and eQ, each of which is computationally complex. Other protocols, such as the MQV protocols require similar computations when implemented over elliptic curves which may result in slow verification when the computing power is limited.
Typically, the underlying curve has the form y2+xy=x3+ax+b and the addition of two points having coordinates (x1,y1) and (x2,y2) results in a point (x3,y3) where:
            x      3        =                            (                                                    y                1                            ⊕                              y                2                                                                    x                1                            ⊕                              x                2                                              )                2            ⊕                                    y            1                    ⊕                      y            2                                                x            1                    ⊕                      x            2                              ⊕              x        1            ⊕              x        2            ⊕              a        ⁢                                  (                  P          ≠          Q                )                        y      3        =                  (                                            y              1                        ⊕                          y              2                                                          x              1                        ⊕                          x              2                                      )            ⊕              (                              x            1                    ⊕                      x            3                          )            ⊕              x        3            ⊕                        y          1                ⁢                                  (                  P          ≠          Q                )            
The doubling of a point i.e. P to 2P, is performed by adding the point to itself so that
            y      3        =                            {                                    x              1              2                        ⊕                          (                                                x                  1                                ⊕                                                      y                    1                                                        x                    1                                                              )                                }                ⁢                  x          3                    ⊕              x        3                        x      3        =                  x        1        2            ⊕              b                  x          1          2                    
It will be appreciated that successive doubling of the point Q produces values for 2Q, 22Q, 23Q . . . 2jQ and that these values may be substituted in the binary representation of the hash value e and added using the above equations to provide the value eQ. At most this would require t doublings and t point additions for at bit representation of e. Similarly the point P may be doubled successively and the values substituted in the representation of s to obtain sP. However, the generation of each of the doubled points requires the computation of both the x and y coordinates and the latter requires a further inversion. These steps are computationally complex and therefore require either significant time or computing power to perform. Substitution in the underlying curve to determine the value of y is not practical as two possible values for y will be obtained without knowing which is intended.
It is therefore an object of the present invention to provide a method and apparatus in which the above disadvantages are obviated or mitigated.